# 03. 删除有序数组中的重复项
from typing import List
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        ans_dict = {}
        ans = 0
        for i in range(len(nums)):
            if nums[i] not in ans_dict:
                ans_dict[nums[i]] = 1
                nums[ans] = nums[i]
                ans += 1
        return ans

# 参考04题后想出的不依赖额外空间的双指针法，用到了有序
class Solution1:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return n
        slow, fast = 1, 1
        while fast < n:
            if nums[slow-1] != nums[fast]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow